#include "Tree.hpp"

int Tree::makeEmpty(Node * & t) {
    if (t == NULL)
        return 0;

    hash_map<string, Node *> & tChildren = t->getVarChildren();
    hash_map<string, Node *>::iterator it = tChildren.begin(),
        end = tChildren.end();

    for ( ; it != end; it++) {
        Node * child = it->second;
        makeEmpty(child);
    }
    // Empty the children.
    tChildren.clear();

    delete t;
    // t must be a reference because of the below.
    t = NULL;

    return 0;
}

// Insert a transaction to the fp-tree. The transaction is already sorted 
// according to decreasing item support values and pruned according to
// minimum support. Each item is inserted one by one to the tree.
int Tree::insert(vector<string> * transaction, int count) {
    vector<string>::iterator it = transaction->begin(),
        end = transaction->end();

    if (it == end)
        return 0;

    Node * next = NULL, * current = root;
    string item;

    for ( ; it != end; it++) {
       item = *it;
       next = current->getNode(item);
       if (next == NULL) {
           Node * child = new Node(item, count);
           current->insertChild(child);
           insertHeaderInfo(child);
           current = child;
       }
       else {
           next->incCount(count);
           current = next;
       }       
    }
    return 0;
}

void Tree::insertHeaderInfo(Node * node) {
    string item = node->getItem();
    hash_map<string, HeaderInfo *>::iterator it = headerTable.find(item);
    hash_map<string, HeaderInfo *>::iterator end = headerTable.end();
    if (it == end) {
        HeaderInfo * hi = new HeaderInfo(item, node, node);
        headerTable[item] = hi;
        headerVector.push_back(hi);
    }
    else {
        HeaderInfo * hi = (*it).second;      
        Node * oldLast = hi->last;
        // Check to make sure no node's next point to themselves. Dangerous.
        // This check is actually not needed.
        if (oldLast != node) {
            oldLast->setNext(node);
            hi->last = node;
        }
    }
}

// The copy assignment operator.
const Tree & Tree::operator=(const Tree & rhs) {
    // Check for alias.
    if (this != &rhs) {
        makeEmpty();
        const Node * rhsRoot = rhs.getRoot();
        root = new Node(rhsRoot->getItem(), rhsRoot->getCount());

        const hash_map<string, Node *> & rhsChildren = rhsRoot->getChildren();
        hash_map<string, Node *>::const_iterator rhsChildrenIt = rhsChildren.begin(),
            rhsChildrenEnd = rhsChildren.end();
        for ( ; rhsChildrenIt != rhsChildrenEnd; rhsChildrenIt++) {
            root->insertChild(duplicate(rhsChildrenIt->second));
        }
    }
    return *this;
}

Node * Tree::duplicate(const Node * cur) {
    Node * toReturn = new Node(cur->getItem(), cur->getCount());
    // Add it to the header table.
    insertHeaderInfo(toReturn);

    const hash_map<string, Node *> & curChildren = cur->getChildren();
    hash_map<string, Node *>::const_iterator curChildrenIt = curChildren.begin(),
        curChildrenEnd = curChildren.end();

    for ( ; curChildrenIt != curChildrenEnd; curChildrenIt++) {
        toReturn->insertChild(duplicate(curChildrenIt->second));
    }
    return toReturn;
}

void Tree::merge(Tree & t) {
    // Merge the trees.
    Node * tRoot = t.getRoot();
    insertSubTree(root, tRoot);

    // Reduce the item counts as well.
    hash_map<string, int> * tItemCountsP = t.getItemCountsP();
    hash_map<string, int>::iterator it = tItemCountsP->begin(), 
        end = tItemCountsP->end();
    for ( ; it != end; it++) {
        itemCounts[it->first] += it->second;
    }
}

void Tree::insertSubTree(Node * fromCurrentTree, Node * fromNewTree) {
    const hash_map<string, Node *> childrenFromNew = fromNewTree->getChildren();
    hash_map<string, Node *>::const_iterator it = childrenFromNew.begin(),
        end = childrenFromNew.end();

    for ( ; it != end; it++) {
        string item = it->first;
        Node * childFromCurrent = fromCurrentTree->getNode(item);
        Node * childFromNew = it->second;
        if (childFromCurrent == NULL) {
            fromCurrentTree->insertChild(duplicate(childFromNew));
        }
        else {
            // Gotta add up the counts and recursively call for the children.
            childFromCurrent->incCount(childFromNew->getCount());
            insertSubTree(childFromCurrent, childFromNew);
        }
    }
}

void Tree::print() {
    hash_map<string, Node *>::const_iterator it = (root->getChildren()).begin(),
        end = (root->getChildren()).end();

    for ( ; it != end; it++) {
        printRec(it->second);
    }
}

void Tree::printRec(Node * n) {
    hash_map<string, Node *>::const_iterator it = (n->getChildren()).begin(),
        end = (n->getChildren()).end();

    for ( ; it != end; it++) {
        printRec(it->second);
    }
}

void Tree::printHeaderTable() {
    hash_map<string, HeaderInfo *>::iterator it = headerTable.begin(),
        end = headerTable.end();

    for ( ; it != end; it++) {
        string item = it->first;
        HeaderInfo hi = *(it->second);
    }
}

void Tree::printHeaderVector() {
    vector<HeaderInfo *>::iterator it = headerVector.begin(),
        end = headerVector.end();

    for ( ; it != end; it++) {
        HeaderInfo hi = **it;

        Node * last;
        for ( Node * temp = hi.first; 
                temp != NULL; temp = temp->getNext()) {
            last = temp;
        }
        if (last != hi.last) {
            cout << "There maybe an error ahead" <<
                "**********************\n**********************" << endl;
        }
    }
}

